package com.gitee.swsk33.algorithms.graph.adtable;

import lombok.Getter;

import java.util.*;

/**
 * 邻接表（有向图）
 */
public class ADTable<T> {

	/**
	 * 顶点表
	 */
	private VertexTable<T>[] vertexList;

	/**
	 * 顶点数
	 */
	@Getter
	private int nodeCount;

	/**
	 * 边数
	 */
	@Getter
	private int arcCount;

	/**
	 * 邻接表构造函数
	 *
	 * @param nodes 传入所有的顶点数组以初始化这个邻接表的顶点表
	 */
	public ADTable(T[] nodes) {
		nodeCount = nodes.length;
		arcCount = 0;
		vertexList = new VertexTable[nodes.length];
		// 初始化边表
		for (int i = 0; i < nodes.length; i++) {
			vertexList[i] = new VertexTable<>();
			vertexList[i].setData(nodes[i]);
			vertexList[i].setFirstEdge(null);
		}
	}

	/**
	 * 将两个顶点连接（链表头插法）
	 *
	 * @param startIndex 要连接的起点下标
	 * @param endIndex   要连接的终点下标
	 */
	public void insertEdge(int startIndex, int endIndex) {
		// 先新建一个边表实例
		EdgeTable table = new EdgeTable();
		// 边表存放被指向的顶点下标
		table.setIndex(endIndex);
		// 执行头插法
		// 先把新边表的下一个指向对应的起点的顶点表的下一个
		table.setNext(vertexList[startIndex].getFirstEdge());
		// 再把对应起点的顶点的下一个指向新边表
		vertexList[startIndex].setFirstEdge(table);
		// 边加一
		arcCount++;
	}

	/**
	 * 获取visit数组中第一个没有被访问的值
	 *
	 * @param visit visit访问数组
	 * @return 第一个没有被访问的值的下标，若全都被访问了则返回-1
	 */
	private int getIndexOfNotVisited(boolean[] visit) {
		for (int i = 0; i < visit.length; i++) {
			if (!visit[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 深度优先遍历-递归部分
	 *
	 * @param visited 访问数组，用于记录哪些下标的点被访问过
	 * @param index   指定开始访问的点的下标
	 */
	private void DFS(boolean[] visited, int index) {
		// 先访问起点并标记其被访问
		visited[index] = true;
		// 这里以输出操作代替访问
		System.out.println(vertexList[index].getData());
		// 遍历访问该点的邻接点
		EdgeTable pointer = vertexList[index].getFirstEdge();
		// 用指针指向这个点对应的链表的每一个边表结点，对每个边表结点对应的点进行递归访问（没访问过的）
		while (pointer != null) {
			if (!visited[pointer.getIndex()]) {
				DFS(visited, pointer.getIndex());
			}
			pointer = pointer.getNext();
		}
	}

	/**
	 * 深度优先遍历-启动部分
	 */
	public void doDFS() {
		// 初始化visited数组、结果列表
		boolean[] visited = new boolean[vertexList.length];
		Arrays.fill(visited, false);
		// 从第一个未访问到的点开始直到全部访问到
		int notVisited;
		while ((notVisited = getIndexOfNotVisited(visited)) != -1) {
			DFS(visited, notVisited);
		}
	}

	/**
	 * 广度优先搜索
	 */
	public void doBFS() {
		// 先初始化visit数组
		boolean[] visit = new boolean[vertexList.length];
		Arrays.fill(visit, false);
		// 实例化一个队列存放已经访问过的点，以便访问它们的邻接点
		Queue<VertexTable<T>> queue = new LinkedList<>();
		// 访问第一个没访问的点，直到全部访问到
		int notVisited;
		while ((notVisited = getIndexOfNotVisited(visit)) != -1) {
			// 先访问这个点
			visit[notVisited] = true;
			queue.offer(vertexList[notVisited]);
			System.out.println(vertexList[notVisited].getData());
			while (!queue.isEmpty()) {
				// 对访问到的点进行广度优先遍历，让访问到的点出队，对他们的邻接点进行访问
				EdgeTable pointer = queue.poll().getFirstEdge();
				// 访问这个点全部邻接点，访问一个就入队一个
				while (pointer != null) {
					queue.offer(vertexList[pointer.getIndex()]);
					visit[pointer.getIndex()] = true;
					System.out.println(vertexList[pointer.getIndex()].getData());
					pointer = pointer.getNext();
				}
			}
		}
	}

	/**
	 * 用于输出
	 */
	@Override
	public String toString() {
		StringBuilder result = new StringBuilder();
		for (VertexTable<T> vertex : vertexList) {
			result.append("value:").append(vertex.getData());
			EdgeTable pointer = vertex.getFirstEdge();
			while (pointer != null) {
				result.append(" -> ").append(vertexList[pointer.getIndex()].getData());
				pointer = pointer.getNext();
			}
			result.append(" -> ").append("^").append("\r\n");
		}
		return result.toString();
	}

}